class Solution(object):
    def findMin(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        def search(left_index, right_index):
            if right_index - left_index < 2:
                return min(nums[left_index], nums[right_index])
            mid_index = (left_index + right_index) // 2
            if nums[mid_index] < nums[right_index]:
                if nums[mid_index] >= nums[left_index]:
                    return nums[left_index]
                else:
                    return search(left_index, mid_index)
            else:
                if nums[mid_index] > nums[right_index]:
                    return search(mid_index + 1, right_index)
                else:
                    if nums[mid_index] == nums[left_index]:
                        return min(search(left_index, mid_index - 1), search(mid_index + 1, right_index))
                    else:
                        if nums[mid_index] < nums[left_index]:
                            return search(left_index, mid_index)
                        else:
                            return nums[left_index]
        return search(0, len(nums) - 1)


data = Solution()
nums = [3, 5, 1]
print(data.findMin(nums))
nums = [10,1,10,10,10]
print(data.findMin(nums))
nums = [2,2,2,0,1]
print(data.findMin(nums))
nums = [3,0,1,1,3]
print(data.findMin(nums))